const obj = {
    self: 1,
    left: {
        self: 2,
        left: {
            self: 4,
            left: {
                self: 89,
            },
            right: {
                self: 6,
                left: {
                    self: 68,
                },
                right: {
                    self: 7,
                }
            }
        },
        right: {
            self: 27
        },
    },
    right: {
        self: 3,
        left: {
            self: 5
        },
        right: {
            self: 16
        }
    }
}

//前序遍历(很简单)
function preOrder(obj) {
    const arr = [obj];
    while (arr.length) {
        const item = arr.pop();

        if (item.right) {
            arr.push(item.right);
        }
        if (item.left) {
            arr.push(item.left);
        }
        console.log(item.self);
    }
}

//中序遍历（较复杂）
function midOder(obj) {
    const arr = [];
    let current = obj;
    while (current || arr.length) {
        while (current) {
            arr.push(current);
            current = current.left;
        }
        current = arr.pop();

        console.log(current.self);
        current = current.right;
    }
}

//后序遍历
function postOrder(obj) {
    const arr = [];
    const source = [obj];
    while (source.length) {
        const item = source.pop();
        if (item.right) {
            source.push(item.right);
        }
        if (item.left) {
            source.push(item.left);
        }
        arr.push(item);
    }
    while(arr.length > 0){
        console.log(arr.pop().self);
    }
}

//层次遍历
function levelOrder(obj) {
    const arr = [obj];
    while (arr.length) {
        const current = arr.shift();
        console.log(current.self);
        if (current.left) {
            arr.push(current.left);
        }
        if (current.right) {
            arr.push(current.right)
        }
    }
}

// preOrder(obj);
postOrder(obj);
// midOder(obj);
// levelOrder(obj);